package com.sympsel.Optimal_Algorithm_OA;


import org.junit.Test;

import java.util.*;

public class TwoPointerDemo {
    public void moveZeroes(int[] nums) {
        int n = nums.length;
        int dest = -1;
        int curr = 0;
        while (curr < n) {
            if (nums[curr] != 0) {
                dest++;
                int temp = nums[curr];
                nums[curr] = nums[dest];
                nums[dest] = temp;
            }
            curr++;
        }

        // int n = nums.length;
        // int j = 0;
        // for (int i = 0; i < n; i++) {
        //     if (nums[i] != 0) {
        //         nums[j++] = nums[i];
        //     }
        // }
        // while (j < n) {
        //     nums[j++] = 0;
        // }
    }

    @Test
    public void test1() {
        int[] nums = {0, 1, 0, 3, 12};
        moveZeroes(nums);
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }

    public void duplicateZeros(int[] arr) {
//        int n = arr.length;
//        int end = 0;
//        int nCopy = n;
//        for (int i = 0; i < nCopy; i++, end++) {
//            if (arr[i] == 0) {
//                nCopy--;
//            }
//        }
//
//        System.out.println("end: " + end);
//        end--;
//        for (int i = n - 1; i > 0; i--, end--) {
////            if (end != -1) {
//            if (arr[end] == 0) {
//                arr[i--] = 0;
//            }
//            arr[i] = arr[end];
////            }
//        }

//        0,1,7,6,0,2,0,7
//        0,0,1,7,6,0,0,2

        int n = arr.length;
        int cntOfZero = 0;
        for (int i : arr) {
            if (i == 0) {
                cntOfZero++;
            }
        }

        for (int i = n - 1, j = cntOfZero + n - 1; j >= 0; i--, j--) {
            if (j < n) {
                arr[j] = arr[i];
            }
            if (arr[i] == 0) {
                j--;
                if (j < n) {
                    arr[j] = 0;
                }
            }
        }
    }

    @Test
    public void test2() {
//        int[] arr = {8,4,5,0,0,0,0,7};
        int[][] arr = {
                {8, 4, 5, 0, 0, 0, 0, 7},
                {1, 0, 2, 3, 0, 4, 5, 0},
                {0, 1, 7, 6, 0, 2, 0, 7},
                {1, 2, 3},
                {0, 0, 0, 0, 0, 0, 0}
        };

        // 0,0,0,0,0,0,0
        // 1, 0, 2, 3, 0, 4, 5, 0
        // 0,1,7,6,0,2,0,7
        // 1, 2, 3
        for (int[] ints : arr) {
            for (int j : ints) {
                System.out.print(j + " ");
            }
            duplicateZeros(ints);
            for (int j : ints) {
                System.out.print(j + " ");
            }
            System.out.println("===============");
        }
    }

    public boolean isHappy(int n) {
        Set<Integer> exists = new HashSet<>();
        while (n != 1 && !exists.contains(n)) {
            int num = 0;

            for (int nCopy = n; nCopy != 0; nCopy /= 10) {
                num += (int) Math.pow(nCopy % 10, 2);
            }

            exists.add(n);
            n = num;
        }
        return n == 1;
    }

    @Test
    public void test3() {
        int[] demo = {
                2, 19
        };
        for (int i : demo) {
            System.out.println(isHappy(i));
        }
    }

    public int maxArea(int[] height) {
        // 暴力解法
//        int n = height.length;
//        int max = 0;
//        for (int i = 0; i < n - 1; i++) {
//            for (int j = i + 1; j < n; j++) {
//                int s = (j - i) * Math.min(height[i], height[j]);
//                if (s > max) {
//                    max = s;
//                }
//            }
//        }
//        return max;

        // 双指针
        int n = height.length;
        int left = 0, right = n - 1;
        int ret = 0;
        while (left < right) {
            int v = (right - left) * Math.min(height[left], height[right]);
            ret = Math.max(ret, v);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return ret;
    }

    @Test
    public void test4() {
        int[][] demo = {
                {1, 8, 6, 2, 5, 4, 8, 3, 7},
                {1, 1}
        };
        for (int[] ints : demo) {
            System.out.println(maxArea(ints));
        }
    }

    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int cnt = 0;

        // int end = nums.length - 1;
        // int left = 0;
        // int right = end - 1;

        //  while (end > 1) {
        //     while (left < right) {
        //         if (nums[left] + nums[right] > end) {
        //             cnt += right - left;
        //             break;
        //         } else {
        //             left++;
        //         }
        //     }
        //     left = 0;
        //     right = --end - 1;
        //    }

        for (int end = nums.length - 1; end > 1; --end) {
            int left = 0;
            int right = end - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[end]) {
                    cnt += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }

        return cnt;
    }

    @Test
    public void test5() {
        int[][] demo = {
                {2, 2, 3, 4},
                {4, 3, 2, 4},
                {1, 1, 1, 1}
        };
        for (int[] ints : demo) {
            System.out.println(triangleNumber(ints));
        }
    }

    public ArrayList<Integer> FindNumbersWithSum(int[] arr, int sum) {
        int n = arr.length;

        int left = 0;
        int right = n - 1;

        while (left < right) {
            int temp = arr[left] + arr[right];
            if (temp > sum) {
                --right;
            } else if (temp < sum) {
                ++left;
            } else {
                final int l = left;
                final int r = right;
                return new ArrayList<>() {{
                    add(arr[l]);
                    add(arr[r]);
                }};
            }
        }

        return new ArrayList<>();
    }

    @Test
    public void test6() {
        int[][] demo = {
                {1, 2, 4, 7, 11, 15},
                {1, 15, 11}
        };
        int[] target = {
                15,
                10
        };
        for (int i = 0; i < demo.length; i++) {
            System.out.println(FindNumbersWithSum(demo[i], target[i]));
        }
    }

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();
        // -4, -1, -1, 0, 1, 2
        int end = nums.length - 1;
        for (int i = end; i > 1; --i) {
            if (i < end && nums[i] == nums[i + 1]) {
                continue;
            }
            int left = 0;
            int right = i - 1;
            while (left < right) {
                int sumOfTwo = nums[left] + nums[right];
                if (sumOfTwo > -nums[i]) {
                    --right;
                } else if (sumOfTwo < -nums[i]) {
                    ++left;
                } else {
                    ret.add(new ArrayList<>(
                            Arrays.asList(nums[left], nums[right], nums[i]))
                    );
                    while (left < right && nums[left] == nums[left + 1]) {
                        ++left;
                    }

                    while (left < right && nums[right] == nums[right - 1]) {
                        --right;
                    }
                    ++left;
                    --right;
                }
            }
        }

        return ret;
    }

    @Test
    public void test7() {
        int[][] demo = {
                {-1, 0, 1, 2, -1, -4},
                {0, 1, 1},
                {0, 0, 0, 0}
        };
        for (int[] ints : demo) {
            System.out.println(threeSum(ints));
        }
    }

    public void threeSum(long[] sortedNums, long target, List<List<Long>> ret, int end, long four) {
        for (int i = end; i > 1; --i) {
            if (i < end && sortedNums[i] == sortedNums[i + 1]) {
                continue;
            }
            int left = 0;
            int right = i - 1;
            while (left < right) {
                long sumOfTwo = sortedNums[left] + sortedNums[right];
                if (sumOfTwo + sortedNums[i] > target) {
                    --right;
                } else if (sumOfTwo + sortedNums[i] < target) {
                    ++left;
                } else {
                    ret.add(new ArrayList<>(
                            Arrays.asList(sortedNums[left], sortedNums[right], sortedNums[i], four))
                    );
                    while (left < right && sortedNums[left] == sortedNums[left + 1]) {
                        ++left;
                    }

                    while (left < right && sortedNums[right] == sortedNums[right - 1]) {
                        --right;
                    }
                    ++left;
                    --right;
                }
            }
        }
    }

    public List<List<Integer>> fourSum(long[] nums, int target) {
        Arrays.sort(nums);
        List<List<Long>> ret = new ArrayList<>();
        int end = nums.length - 1;
        for (int i = end; i > 2; --i) {
            if (i < end && nums[i] == nums[i + 1]) {
                continue;
            }
            threeSum(nums, target - nums[i], ret, i - 1, nums[i]);
        }

        List<List<Integer>> result = new ArrayList<>();
        for (List<Long> list : ret) {
            List<Integer> intList = new ArrayList<>();
            for (Long val : list) {
                if (val > Integer.MAX_VALUE || val < Integer.MIN_VALUE) {
                    throw new ArithmeticException("Value out of Integer range: " + val);
                }
                intList.add(val.intValue());
            }
            result.add(intList);
        }

        return result;

    }

    @Test
    public void test8() {
        long[][] demo = {
                {1, 0, -1, 0, -2, 2},
                {2, 2,2,2,2},
                {1000000000,1000000000,1000000000,1000000000}
        };
        int[] target = {
                0,
                8,
                -294967296
        };
        for (int i = 0; i < demo.length; i++) {
            System.out.println(fourSum(demo[i], target[i]));
        }
    }
}
